1. Field of the Invention
This invention relates to computer systems, and more particularly to programmatically generating audio file playlists.
2. Description of the Related Art
In previous decades, a listener's collection of audio selections (e.g., music) was pre-organized onto albums, tapes, and/or CDs (for simplicity, referred to collectively herein as “albums”). When a listener wanted to listen to an audio selection, the listener would select an album, cue it up, and listen to it. Today, however, audio file collections may consist of hundreds, thousands, or even millions of individual digital audio files stored as individual files on a computer (e.g., on personal computers, servers, Web servers, etc) or other device such as a portable audio file player (e.g., an MP3 player).
An audio file format is a file format for digitally storing audio data on a computer system or other device or media. There are many file formats for digitally storing audio files. These file formats come in two major groups of audio file formats:                Lossless compression formats (e.g., WAVEform audio format (WAV), PCM, TTA, Free Lossless Audio Codec. (FLAC), AU, Broadcast Wave Format (BWF)).        “Lossy” compression formats (e.g., MPEG Layer 3 Audio File (MP3), Ogg Vorbis (OGG), Windows Media Audio (WMA), Advanced Audio Coding (AAC)).        
Selecting and organizing subsets of digital audio files into interesting, human-generated “playlists”, that is, ordered lists or sequences of audio files, is a common task of the listener. However, using conventional mechanisms for manually generating playlists, the task may be tedious and difficult, especially when the audio file collection is large and diverse, and when at least some of the devices used as audio file players are small, handheld devices with correspondingly limited user interfaces.
There exists a large number of human-generated playlists. There are, for example, many Web sites on the Internet on which large collections of human-generated playlists may be found. These playlists may be created, for example, by professional DJs, as well as by amateurs with a love of a ‘good mix’, uploaded to a Web site or Web sites, from where other interested listeners may download interesting playlists for their personal use.
As audio file collections continue to grow, as portable, digital audio file players such as MP3 players continue to become more popular, and as the ability to play digital audio files is incorporated into various other devices such as cell phones, the demand for automated playlist generation mechanisms, to free the user from the need to manually generate playlists, may continue to grow. A goal of automated playlist generation is to automatically generate playlists of songs that may be interesting or pleasing to listeners with a minimum amount of input from the listeners.
A number of mechanisms have been developed to automate the generation of playlists. Some conventional automated playlist generators may generate playlists of audio files randomly selected from an audio file collection, for example a playlist of randomly-selected song from various artists, from a particular artist, or from a particular genre. Some conventional automated playlist generators may provide time-based playlist generation. For example, these playlist generators may generate playlists of audio files that have not been played in a while, or that include a set of audio files that have been most recently played. Some conventional automated playlist generators may provide frequency-based playlist generation. For example, these playlist generators may generate playlists of audio files that have been most frequently played, or that have been infrequently played. Some conventional automated playlist generators may provide content-based playlist generation. For example, these playlist generators may generate playlists of songs that sound similar, for example according to acoustics or clarity. Some conventional automated playlist generators may provide rules-based playlist generation. For example, these playlist generators may provide rules to play top-rated songs (five-star songs). Some rules-based playlist generators may be configured to generate playlists from a combination of one or more of the above, e.g. 35% random, 35% five-star, and 30% of songs never heard. All very mechanical on how they select songs.
However, these conventional automated playlist generation mechanisms typically do not take into account the many human factors involved in making a playlist enjoyable and interesting. Playlists are more than just collections of audio files. The juxtaposition of artists, styles, themes and mood may make the whole greater than the sum of its parts. Conventional automated playlist generation mechanisms typically generate playlists using simple criteria such as acoustic similarity, random selection within a genre, alphabetical by title, and so on. These simple criteria tend to result in playlists that lack the interesting juxtapositions of songs, the “human element”, expected by listeners. As such, playlists generated by conventional automated playlist generation mechanisms tend to be less appealing and interesting than those generated by knowledgeable human listeners. The qualities that make a playlist ‘interesting’ are difficult to quantify. For example, audio files of digitized music may be related by musical theme, lyrical theme, artist, genre, instrumentation, rhythm, tempo, period (e.g., 60s music), energy etc. The subtleties involved are beyond what can be expected of a machine to understand using the conventional automated playlist generation techniques described above.
N-Gram Statistical Algorithms
N-Gram statistical models are well-known methods that have proved to be useful, for example, in modeling language in speech recognition. N-Gram language models are typically used to predict the most likely set of next words. An N-gram in a language model is a subsequence of n characters from a given string after removing all spaces. By converting a string to N-grams, the string may be embedded in a vector space, thus allowing the string to be compared to other strings in an efficient manner. N-grams may be used, for example, to break a large collection of text into sequential groups of strings including two (2-gram, or bi-gram), three (3-gram, or tri-gram), or more characters in order to assess the probability of a character sequence (a string) in the collection. When this is done for a large collection of text, it becomes possible to statistically probabilistically estimate the most common occurrence of given strings in the collection of text. N-grams may also be applied to collections of other types of data than text to perform probability calculations for occurrences of data instances in the collections.